package stack;

import java.util.Stack;

public class largestRectangleArea {
    public int largestRectangleArea(int[] heights) {
        int[] newHeight = new int[heights.length + 2];
        System.arraycopy(heights, 0, newHeight, 1, heights.length);
        newHeight[heights.length + 1] = 0;
        newHeight[0] = 0;
        Stack<Integer> stack = new Stack<>();
        int result = 0;
        for (int i = 0; i < newHeight.length; i++) {
            while (!stack.isEmpty() && newHeight[i] < newHeight[stack.peek()]){
                int mid = stack.pop();
                if (!stack.isEmpty()){
                    int h = newHeight[mid];
                    int w = i - stack.peek() - 1;
                    result = Math.max(result, h * w) ;
                }
            }
            stack.push(i);
        }
        return result;
    }
}
